The rapid growth of the internet has led to an increased demand for devices that can perform high speed packet forwarding, such as high performance routing devices. These routing devices receive packets and determine the appropriate next hop, e.g. output port, for the received packets. The appropriate output port is generally determined by performing an address lookup on a routing table, e.g. an internet protocol (IP) address lookup, with respect to the destination address of the packet. The routing table may include a prefix corresponding to each destination subnet and a next hop for delivering the packet to its intended destination. Since the prefix for each entry in the routing table may specify a network, the destination address may match more than one entry in the routing table, e.g. a network, a subnet of the network, etc. However, the most specific table entry that matches the destination address, e.g. the entry for which the largest number of leading address bits, e.g. most significant address bits, in the table entry match those of the destination address, should be the table entry that is selected for the packet, and may be referred to as the longest prefix match for the destination address.
The algorithm used by a routing device to determine the longest prefix match may contribute significantly to the latency of the routing device, and may even be a bottleneck for the routing device. Benchmarks used to measure the performance of an algorithm used by a routing device to determine the longest prefix match may include the number of memory accesses needed by the algorithm to identify the longest prefix match (in the worst and average cases), and the memory consumption needed by the algorithm to store and process the routing table. One algorithm that may be used by a routing device to determine the longest prefix match is a tree bitmap (TBMP) algorithm. In the TBMP algorithm, prefixes of a routing table are stored in a tree bitmap data structure that is searched for the longest prefix match. The tree bitmap data structure is searched in an order that starts with the shortest stored prefix and traverses down to the longest prefixes. Thus, the TBMP algorithm may require more memory accesses to match a longer prefix to a given packet's destination address than to match a shorter prefix. Another algorithm that may be used is a binary hash searching on prefix length (BSOL) algorithm. In the BSOL algorithm, prefixes of a routing table are hashed into hash tables that are associated with the length of the prefixes and that are subsequently searched for the longest prefix match. The BSOL algorithm may associate one hash table with each prefix length; thus, the memory consumption of the BSOL algorithm may increase significantly for large routing tables with prefixes having many different lengths.